#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 优先队列优化
int prim(int n, vector<vector<int>>& cost) {
    // 邻接表
    vector<vector<pair<int, int>>> graph(n + 1);
    for (auto& e : cost) {
        graph[e[0]].emplace_back(e[2], e[1]);
        graph[e[1]].emplace_back(e[2], e[0]);
    }

    vector<bool> vi(n + 1, 0);
    priority_queue<pair<int,int>, vector<pair<int,int>> ,greater<>> que;
    
    int ans = 0;
    que.emplace(0, 1);
    while(!que.empty()){
        int dis = que.top().first;
        int to = que.top().second;
        que.pop();
        if(vi[to]) continue;
        vi[to] = 1;
        ans += dis;
        for(auto& e : graph[to]) que.emplace(e.first, e.second);
    }
    return ans;
}

// 无优化版本
int prim(int n, vector<vector<int>>& cost) {
    // 邻接表
    vector<vector<pair<int, int>>> graph(n + 1);
    for (auto& e : cost) {
        graph[e[0]].emplace_back(e[2], e[1]);
        graph[e[1]].emplace_back(e[2], e[0]);
    }

    vector<int> lowcost(n + 1, 0x3f3f3f3f);
    vector<bool> vi(n + 1, 0);

    int k = n, ans = 0;
    lowcost[1] = 0;
    while (k--) {
        int mincost = 0x3f3f3f3f;
        int minindex = -1;
        for (int i = 1; i <= n; i++) {
            if (!vi[i] && lowcost[i] < mincost) {
                mincost = lowcost[i];
                minindex = i;
            }
        }

        vi[minindex] = 1;
        ans += mincost;

        // 更新 lowcost
        for (auto& e : graph[minindex]) {
            lowcost[e.second] = min(lowcost[e.second], e.first);
        }
    }

    return ans;
}